//"单词搜索"
class Solution {
    int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
    bool check[7][7];
    int _x,_y,_n;
public:
    bool exist(vector<vector<char>>& board, string word) {
        _x = board.size();
        _y = board[0].size();
        _n = word.size();

        for(int i =0; i < _x; i++)
            for(int j = 0; j <_y; j++)
                if(board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if(dfs(board,word,i,j,1))   return true;
                    check[i][j] = false;
                }

        return false;
    }

    bool dfs(vector<vector<char>>& board,string word,int i,int j,int n)
    {
        if(n == _n)
            return true;

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < _x && y >= 0 && y < _y && !check[x][y] && board[x][y] == word[n])
            {
                check[x][y] = true;
                if(dfs(board,word,x,y,n + 1))   return true;
                check[x][y] = false;
            }
        }   

        return false;
    }
};

//黄金矿工
class Solution {
    int ret = 0,m,n;
    bool vis[16][16];
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size(),n = grid[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] && !vis[i][j])
                {
                    vis[i][j] = true;
                    dfs(grid,i,j,grid[i][j]); 
                    vis[i][j] = false;
                }
                    
            }
    return ret;    
    }

    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    void dfs(vector<vector<int>>& grid,int i, int j,int sum)
    {
        ret = max(ret,sum);

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k],y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != 0 && !vis[x][y])
            {
                vis[x][y] = true;
                dfs(grid,x,y,sum + grid[x][y]);
                vis[x][y] = false;
            }            
        }
    }
};
